package hot100.logos81To90;

import java.util.Arrays;

/**
 * @author logos
 * date 2025/7/18 11:32
 * @version v1.0
 * @Package hot100.logos81To90
 */
public class logos85 {


    /**
     * 85. 零钱兑换
     * https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution1 {
        public int coinChange(int[] coins, int amount) {
            int n = coins.length;
            int[][] dp = new int[n + 1][amount + 1];
            Arrays.fill(dp[0], Integer.MAX_VALUE / 2);
            dp[0][0] = 0;
            for (int i = 0; i < n; i++) {
                for (int c = 0; c <= amount; c++) {
                    if (c < coins[i]) {
                        dp[i + 1][c] = dp[i][c];
                    } else {
                        dp[i + 1][c] = Math.min(dp[i][c], dp[i + 1][c - coins[i]] + 1);
                    }
                }
            }
            int ans = dp[n][amount];
            return ans < Integer.MAX_VALUE / 2 ? ans : -1;
        }
    }

    class Solution2 {
        public int coinChange(int[] coins, int amount) {
            int[] dp = new int[amount + 1];
            Arrays.fill(dp, Integer.MAX_VALUE / 2);
            dp[0] = 0;
            for (int x : coins) {
                for (int c = x; c <= amount; c++) {
                    dp[c] = Math.min(dp[c], dp[c - x] + 1);
                }
            }
            int ans = dp[amount];
            return ans < Integer.MAX_VALUE / 2 ? ans : -1;
        }
    }
}
